翻訳と辞書
Words near each other
・ Bit twiddler
・ BIT UAV
・ BIT Zone Station
・ Bit, byte, gebissen
・ Bit-count integrity
・ Bit-flipping attack
・ Bit-hilani
・ Bit-Istar
・ Bit-length
・ Bit-level parallelism
・ Bit-na
・ Bit-O-Honey
・ Bit-oriented protocol
・ Bit-paired keyboard
・ Bit-Phalanx
Bit-reversal permutation
・ Bit-sequence independence
・ Bit-serial architecture
・ Bit-stream access
・ Bit-stream transmission
・ Bit-string physics
・ Bit-synchronous operation
・ Bit-tech
・ Bit-Twist
・ Bit.Trip
・ Bit.Trip Beat
・ Bit.Trip Complete
・ Bit.Trip Core
・ Bit.Trip Fate
・ Bit.Trip Flux


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Bit-reversal permutation : ウィキペディア英語版
Bit-reversal permutation
In applied mathematics, a bit-reversal permutation is a permutation of a sequence of ''n'' items, where ''n'' = 2''k'' is a power of two. It is defined by indexing the elements of the sequence by the numbers from 0 to ''n'' − 1 and then reversing the binary representations of each of these numbers (padded so that each of these binary numbers has length exactly ''k''). Each item is then mapped to the new position given by this reversed value. The bit reversal permutation is an involution, so repeating the same permutation twice returns to the original ordering on the items.
==Example==
Consider the sequence of eight letters ''abcdefgh''. Their indexes are the binary numbers 000, 001, 010, 011, 100, 101, 110, and 111, which when reversed become 000, 100, 010, 110, 001, 101, 011, and 111.
Thus, the letter ''a'' in position 000 is mapped to the same position (000), the letter ''b'' in position 001 is mapped to the fifth position (the one numbered 100), etc., giving the new sequence ''aecgbfdh''. Repeating the same permutation on this new sequence returns to the starting sequence.
Writing the index numbers in decimal (but, as above, starting with position 0 rather than the more conventional start of 1 for a permutation), the bit-reversal permutations of size 2''n'', for ''n'' = 0, 1, 2, 3, ... are
: 0
: 0 1
: 0 2 1 3
: 0 4 2 6 1 5 3 7
: 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
Each permutation in this sequence can be generated by concatenating two sequences of numbers: the previous permutation, doubled, and the same sequence with each value increased by one.
Thus, for example doubling the length-4 permutation gives , adding one gives , and concatenating these two sequences gives the length-8 permutation .

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Bit-reversal permutation」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.